package com.github.yangyishe.p300;

import com.github.yangyishe.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 236. 二叉树的最近公共祖先
 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 * 输出：3
 * 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
 * 示例 2：
 *
 *
 * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 * 输出：5
 * 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
 * 示例 3：
 *
 * 输入：root = [1,2], p = 1, q = 2
 * 输出：1
 *
 *
 * 提示：
 *
 * 树中节点数目在范围 [2, 105] 内。
 * -109 <= Node.val <= 109
 * 所有 Node.val 互不相同 。
 * p != q
 * p 和 q 均存在于给定的二叉树中。
 */
public class Problem236 {
    public static void main(String[] args) {
        Integer[] root=new Integer[]{3,5,1,6,2,0,8,null,null,7,4};
//        Integer[] root=new Integer[]{1,2};
        TreeNode instanceNew = TreeNode.getInstanceNew(root);
        TreeNode p=new TreeNode(4);
        TreeNode q=new TreeNode(5);

        Problem236 problem236 = new Problem236();
        TreeNode treeNode = problem236.lowestCommonAncestor2(instanceNew, p, q);
        System.out.println(treeNode);
    }

    /**
     * 思路:
     * 创建两个链表, 分别记录root到目标节点的路径
     * 再寻找其中相似的部分
     *
     * 缺点: 浪费了遍历前面节点的信息, 此处遍历了两次
     *
     * 思路2:
     * 进行后序遍历, 同时对两个树节点进行检索.
     * 当第一个节点找到后, 添加一个数字记录n=0
     * 仍按照原来的顺序遍历父节点
     * 在父节点基础上, 每进行一次右序遍历, 则n+1
     * 从右序遍历中跳出, 则n-1
     * 当找到第二个节点时, 跳出递归, 直到n=0, 此时获得的节点, 就是p和q的公共节点
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        LinkedList<TreeNode> pList=new LinkedList<>();
        LinkedList<TreeNode> qList=new LinkedList<>();
        preOrder(root,p,pList);
        preOrder(root,q,qList);

        int minSize=Math.min(pList.size(),qList.size());
        TreeNode lastNode=null;
        TreeNode tmp;
        for(int i=0;i<minSize;i++){
            tmp=pList.removeFirst();
            if(tmp.val==qList.poll().val){
                lastNode=tmp;
            }else{
                break;
            }
        }

        return lastNode;
    }

    private List<TreeNode> pList=new ArrayList<>();
    private List<TreeNode> qList=new ArrayList<>();

    public boolean preOrder(TreeNode root, TreeNode target, LinkedList<TreeNode> historyList){
        if(root==null){
            return false;
        }
        historyList.add(root);
        if (root.val==target.val) {
            return true;
        }
        boolean leftFind=preOrder(root.left,target,historyList);
        if(leftFind){
            return true;
        }
        boolean rightFind=preOrder(root.right,target,historyList);
        if(rightFind){
            return true;
        }
        historyList.removeLast();
        return false;
    }



    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        postOrder(root,p,q);
        return target;
    }


    private int findCount;
    private int lastNodeVal;
    private int rightDeepLevel;
    private TreeNode target=null;

    public void postOrder(TreeNode root,TreeNode p,TreeNode q){
        if(root==null||target!=null){
            return;
        }
        postOrder(root.left,p,q);
        if(findCount>0&&rightDeepLevel>=0){
            rightDeepLevel++;
        }
        postOrder(root.right,p,q);
        if(findCount>0&&rightDeepLevel>0){
            rightDeepLevel--;
        }

        if(findCount==0){
            if(root.val==p.val||root.val==q.val){
                findCount=1;
                if(root.val==p.val){
                    lastNodeVal=q.val;
                }else{
                    lastNodeVal=p.val;
                }
            }
        }else if(findCount==1){
            if(root.val==lastNodeVal){
                findCount=2;
            }
        }
        if(findCount==2&&rightDeepLevel==0&&target==null){
            target=root;
        }


    }

}
